package day_7_5;

public class Main1 {
    /**
     * 109. 有序链表转换二叉搜索树
     * https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }

    public TreeNode buildTree(ListNode left,ListNode right) {
        if(left == right) {
            return null;
        }
        // 计算中心节点
        ListNode mid = getMid(left,right);
        // 每次把中心节点当为根节点
        TreeNode root = new TreeNode(mid.val);
        // 之后处理左面和右面，这里的right是选不上的，所以传right值需要一个大于区间的一个节点
        // 比如一开始传入的null，是到不了的，只是进行去计算中心节点
        root.left = buildTree(left,mid);
        root.right = buildTree(mid.next,right);
        return root;
    }

    public ListNode getMid(ListNode left,ListNode right) {
        // 对于链表，进行快慢指针的时候，slow最后的位置就是中心节点
        ListNode fast = left;
        ListNode slow = left;
        while(fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
